Several control systems employed by vehicles, either autonomous vehicles or vehicles executing in autonomous-driving mode, predict future, safe motions of the vehicle toward some target state, both in order to avoid obstacles, such as other vehicles or pedestrians, but also to optimize some criteria associated to the operation of the vehicle. The target state can either be a fixed location, a moving location, a velocity vector, a region, or a combination thereof. The surroundings, such as road edges, pedestrians, and other vehicles, are sensed by the sensors of the vehicle and/or are at least partially known by a priori given information. However, the sensor information is noisy and uncertain, the exact parameters of the vehicle are unknown, and the environment is only partially known. The control of the vehicle should therefore account for such uncertainties.
For example, if an autonomous road vehicle travels along a road segment, the control system of the autonomous vehicle can generate a motion that minimizes one or combinations of deviations from the middle of the lane and speed variations to provide a smooth ride for the passenger and to provide a smooth traffic flow. The sensors of the vehicle detect potential obstacles on the road. The location and velocity of the obstacles are uncertain, due to sensing noise and other sources of uncertainty. The vehicle control system should take the uncertainty into account when computing suitable accelerations and steering input for the vehicle, and the corresponding resulting motion, to avoid unnecessary jumps in control inputs or other unwanted behaviors of the vehicle.
Since the models of the vehicle and the environment used by some control systems of the autonomous vehicle are only simplified mathematical descriptions of the real world, the predicted future motion must be computed fast, such that it can be updated in real time whenever necessary. Therefore, the motion needs to be computed recursively, either at a fixed update rate or whenever new sensor information arrives.
Several systems determine either the path U.S. Pat. No. 8,666,548 or the motion of the vehicle by generating random configurations or control inputs U.S. Pat. No. 7,447,593, US 88825207, and connect different random samples to each other, to grow a tree of possible motions. When only considering predictions of future paths, the computational complexity of the method is reduced, but it can result in a nondrivable path. On the other hand, when motions of the vehicle are predicted, the quality of the motion is determined by evaluating the entire motion. The result is either that the quality of the motions cannot be guaranteed in real-time operation, or that the motion the autonomous vehicle should follow is not determined sufficiently fast, or a combination of the both.
A cause of the lack of quality of motion in combination with computational/memory load is that the quality of the motion is determined by investigating the entire motion, from initial state to target state. Therefore, the tree of possible motions becomes unnecessarily large. In such a case, the computational/memory load can be overwhelming.
Fast computations and reliable performance are ubiquitous in several applications. For example, consider a situation when a road-bound autonomous vehicle travels on a highway and a future motion cannot be found. The predicted motion should not only be safe, but it should also be computed by considering different situations. For example, consider a scenario where the vehicle operates on a road with two lanes and there are two other vehicles present; one in front of the car and one vehicle approaching from behind in the other lane. In such a scenario, the motion must be determined by deciding whether to slow down, stay behind, or initiate overtaking.